817F - MEX Queries - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
int kaf=(1<<19);
struct segment{
	struct node{
		long long ted,sum,lazys,lazyx;
		node(){
			ted=sum=0;
			lazyx=0;
			lazys=-1;
		}
	};
	node seg[(1<<20)];
	void build(int i=1){
		if((i<<1)>=(1<<20)){
			seg[i].ted=1;
			return ;
		}
		build((i<<1));
		build((i<<1)^1);
		seg[i].ted=seg[(i<<1)].ted+seg[(i<<1)^1].ted;
		return ;
	}
	void calc(int i){
		if((i<<1)>=(1<<20)){
			return ;
		}
		int len=seg[i].ted;
		int cnt=seg[(i<<1)].sum;
		if(seg[(i<<1)].lazys!=-1){
			if(seg[(i<<1)].lazys==0){
				cnt=0;
			}
			else{
				cnt=len/2;
			}
		}
		if(seg[(i<<1)].lazyx==1){
			cnt=(len/2)-cnt;
		}
		seg[i].sum=cnt;
		cnt=seg[(i<<1)^1].sum;
		if(seg[(i<<1)^1].lazys!=-1){
			if(seg[(i<<1)^1].lazys==0){
				cnt=0;
			}
			else{
				cnt=len/2;
			}
		}
		if(seg[(i<<1)^1].lazyx==1){
			cnt=(len/2)-cnt;
		}
		seg[i].sum+=cnt;
		return ;
	}

	void shift(int i){
		if((i<<1)>=(1<<20)){
			return ;
		}
		if(seg[i].lazys==-1&&seg[i].lazyx==0){
			return ;
		}
		if(seg[i].lazys!=-1){
			seg[(i<<1)].lazyx=0;
			seg[(i<<1)^1].lazyx=0;
			seg[(i<<1)].lazys=seg[i].lazys;
			seg[(i<<1)^1].lazys=seg[i].lazys;
			seg[i].lazys=-1;
		}
		seg[(i<<1)].lazyx^=seg[i].lazyx;
		seg[(i<<1)^1].lazyx^=seg[i].lazyx;
		seg[i].lazyx=0;
		return calc(i);
	}

	void upd1(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl)
		{
			return ;
		}
		shift(i);
		if(l>=tl&&r<=tr){
			seg[i].lazys=1;
			seg[i].lazyx=0;
			return ;
		}
		int m=(l+r)>>1;
		upd1((i<<1),l,m,tl,tr);
		upd1((i<<1)^1,m+1,r,tl,tr);
		calc(i);
		return ;
	}	
	void upd2(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl)
		{
			return ;
		}
		shift(i);
		if(l>=tl&&r<=tr){
			seg[i].lazys=0;
			seg[i].lazyx=0;
			return ;
		}
		int m=(l+r)>>1;
		upd2((i<<1),l,m,tl,tr);
		upd2((i<<1)^1,m+1,r,tl,tr);
		calc(i);
		return ;
	}
	void upd3(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl)
		{
			return ;
		}
		shift(i);
		if(l>=tl&&r<=tr){
			seg[i].lazyx^=1;
			return ;
		}
		int m=(l+r)>>1;
		upd3((i<<1),l,m,tl,tr);
		upd3((i<<1)^1,m+1,r,tl,tr);
		calc(i);
		return ;
	}
	int pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl){
			return -1;
		}
		shift(i);
		int cnt=seg[i].sum;
		if(seg[i].lazys!=-1){
			if(seg[i].lazys==0){
				cnt=0;
			}
			else{
				cnt=r-l+1;
			}
		}
		if(seg[i].lazyx==1){
			cnt=r-l+1-cnt;
		}
		if(cnt==r-l+1){
			return -1;
		}
		if(l==r){
			return l;
		}
		int m=(l+r)>>1;
		int ret=pors((i<<1),l,m,tl,tr);
		if(ret!=-1){
			return ret;
		}
		ret=pors((i<<1)^1,m+1,r,tl,tr);
		return ret;
	}
}seg;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int q;
	cin>>q;
	seg.build();
	vector<pair<int,pair<long long,long long>>>allq(q);
	vector<long long>allind;
	for(int i=0;i<q;i++){
		cin>>allq[i].first>>allq[i].second.first>>allq[i].second.second;
		allind.push_back(allq[i].second.first);
		allind.push_back(allq[i].second.second);
		allind.push_back(allq[i].second.second+1);
	}
	allind.push_back(1);
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	for(int i=0;i<q;i++){
		int tt;
		tt=allq[i].first;
		int u,v;
		u=lower_bound(allind.begin(),allind.end(),allq[i].second.first)-allind.begin();
		v=lower_bound(allind.begin(),allind.end(),allq[i].second.second)-allind.begin();
		if(tt==1){
			seg.upd1(1,0,kaf-1,u,v);
		}
		if(tt==2){
			seg.upd2(1,0,kaf-1,u,v);
		}
		if(tt==3){
			seg.upd3(1,0,kaf-1,u,v);
		}
		int res=seg.pors(1,0,kaf-1,0,(int)allind.size());
		cout<<allind[res]<<"\n";
	}
}